import com.sun.jdi.PathSearchingVirtualMachine;

import java.sql.Struct;
import java.util.ArrayList;
import java.util.List;

/**
 * @author 21195
 * @version v1.0
 * @package PACKAGE_NAME
 * @description:
 * @date 2019/8/21 17:22
 **/
public class Solution {
    public static void main(String[] args) {
        int[] i = {1, 5, 4, 6, 11, 33, 12, 34, 53, 32};
        System.out.println("冒泡排序的结果：");
        maopao(i);
        System.out.println();
        System.out.println("选择排序的结果：");
        xuanze(i);
        System.out.println();
        System.out.println("插入排序的结果：");
        charu(i);
        System.out.println();
        System.out.println("希尔排序的结果：");
        xier(i);

    }

    private static void maopao(int[] x) {
        for (int i =0; i < x.length; i++){
            for (int j=i+1; j<x.length; j++ ){
                if (x[i]>x[j]){
                    int temp = x[i];
                    x[i] = x[j];
                    x[j] = temp;
                }
            }
        }
        for (int i : x){
            System.out.print(i+" ");
        }
    }

    private static void xuanze(int[] x) {
        for (int i = 0; i < x.length; i++) {
            int lowerInder = i;
            //找出最小的索引
            for (int j = i + 1; j < x.length; j++) {
                if (x[j] < x[lowerInder]){
                    lowerInder = j;
                }

            }
            //交换
            int temp = x[i];
            x[i] = x[lowerInder];
            x[lowerInder] = temp;

        }
        for (int i : x) {
            System.out.print(i + " ");
        }
    }

    private static void charu(int[] x) {
        for (int i = 0; i < x.length; i++) {
            //i 从一开始，因为第一个数已经是排好序的啦
            for (int j = i; j > 0 ; j--) {
                if (x[j] < x[j -1]){
                    int temp = x[j];
                    x[j] = x[j-1];
                    x[j-1] = temp;

                }

            }


        }
        for (int i : x){
            System.out.print(i + " ");
        }
    }

    private static void xier(int[] x) {
        //分组
        for (int increment = x.length / 2; increment > 0; increment /= 2){
            //每个组内排序
            for (int i = 0; increment < x.length; i++) {
                int temp = x[i];
                int j = 0;
                for (j = i; j>= increment; j -= increment){
                    if (temp < x[j - increment]){
                        x[j] = x[j - increment];
                    }else {
                        break;
                    }
                }
                x[j] = temp;

            }
        }
            for (int i : x){
                System.out.print( i + " ");
            }
    }

    public static void quickSort(int [] a, int lo0, int hi0){
        int lo = lo0;
        int hi = hi0;
        if (lo>=hi){
            return;
        }
        //确定指针方向的逻辑变量
        boolean transfer = true;

        while ( lo != hi){
            if (a[lo]> a[hi]){
                //交换数字
                int temp = a[lo];
                a[lo] = a[hi];
                a[hi]= temp;
                //决定下标移动，还是上标移动
                transfer = (transfer == true) ? false :true;
            }
            //将指针向前或者向后移动
            if (transfer){
                hi--;
            }else {
                lo++;
            }
        }
        //将数组分开两半，确定每个数字的正确位置
        lo--;
        hi++;
        quickSort(a, lo0,lo);
        quickSort(a,hi,hi0);
    }


}

